The present invention is directed to methods and apparatus for compression of digital information, for uses such as digital ink and electronic images, as well as more generalized compression and reconstruction applications.
Recently, there has been an explosion in the market for very small computer devices that are highly portable, pocketable or even wearable. Entering textual information into these devices, however, is a challenge. Because of their small size, many of these devices cannot support a full keyboard. A natural way to enter information into such a small device is by using an electronic digitizer such as a pen or stylus to write data directly on the display of the computer. A small computer that interprets handwriting input via a pen is often referred to as a xe2x80x9cpen-basedxe2x80x9d computer. As shown in FIG. 1, a pen-based computer system 10 includes a display 12 and a writing instrument, such as a pen 14 or stylus. A user can input information by xe2x80x9cwritingxe2x80x9d directly on the display 12. In a typical pen-based computer system 10, the user touches the pen 14 to the display 12 and writes as if on a piece of paperxe2x80x94that is, by making a series of pen strokes to form letters, words, drawings or other patterns. A resulting line or curve appears on the display 12, following the path of travel of the pen point so that the pen strokes appear on the display 12 as digital xe2x80x9cinkxe2x80x9d just as handwritten ink would appear on a notebook page. Thus, by digital ink, it is meant the dynamic trace produced by the user when using a writing device to enter information into a computer device, such as a pen-based computer. A pen-based computer system 10 may capture digital ink in the form of one or more strokes. A stroke is a line or curve between the point where the tip of the stylus makes contact with the writing surface and the point where the tip of the stylus leaves the writing surface. Typically, the pen based computer system 10 digitizes the position of pen 14 or stylus as a function of time to create a digital ink vector.
The pen-based computer system 10 typically samples points along each handwritten stroke at a predetermined sampling frequency. Pen-based computer systems may typically sample handwritten data at a rate of up to 200 sampled points per second. If the computer sampling rate is constant, the number of sampled points along a stroke varies inversely with the speed with which the graphic data is handwritten: the faster the handwriting, the fewer the number of sampled points along the stroke; and the slower the handwriting, the greater the number of sampled points along the stroke. Further, the higher the sampling rate, the greater the number of sampled points per stroke, and the lower the sampling rate, the fewer the number of samples points per stroke. For example, at a sampling rate of 100 points per second, stroke 42 in FIG. 2 contains 1000 sampled points if it takes the user one second to write. A typical page of digital ink may contain hundreds of strokes and tens of thousands of sampled points.
The pen-based computer system 10 includes a central processing unit (CPU) that receives the sampled points as a data stream and stores the points in memory, such as dynamic random access memory (DRAM) as shown in FIG. 3. The points may be further processed by software routines stored in flash memory as shown in FIG. 3. Further, the pen-based computer system is often wirelessly connected to a host computer system such that the digital ink may be transmitted from the pen-based computer 10 to the remote computer. If the digital ink is transmitted as generated by the pen-based computer 10, then a large number of sampled points need to be transferred. For example, in uncompressed form, the 1000 sampled points of stroke 42 in FIG. 2 comprises 4000 bytes, where each point is represented as 4 bytes.
A particular problem with having such large data streams is that the memory storage requirements are large. Being able to compress the digital ink allows for less memory to be utilized in the pen-based computer system. This in turn, allows for the pen-based computer system to be designed and manufactured smaller. Thus, it would be desirable for a pen-based computer system to store digital ink efficiently and thus operate free of excessive memory. Another problem with large data streams is that it takes longer to transmit to a remote computer, particularly when using low-bandwidth communication channels such as wireless modems. Generally, transferring digital ink or other image data across a wireless link may take a significant amount of time, which becomes a xe2x80x9cbottleneckxe2x80x9d, or limiting factor for the system performance. Waiting for the system fully render and transfer the ink may impede or interrupt the user""s work flow or train of thought, or may be simply frustrating and irritating to the user. Thus, it would be desirable for a pen-based computer system to transmit digital ink efficiently and thus operate more quickly.
To reduce the size of the data stream, pen-based computers may perform compression on the sampled points of the digital ink to compactly represent the data. It is known in the art to store compression software in a pen-based computer system and have the CPU execute the software to perform compression of the data stream. If the digital ink when captured by the display takes X bytes of storage in Cartesian or vector coordinates, compression will reduce the X bytes to C*X bytes where C less than 1. C represents the compression ratio, or amount of compression performed by the compression software. Thus, if C=0.50, then a captured digital ink of 1000 bytes may be reduced to 500 bytes by performing compression on the captured data stream.
The compressed data stream will eventually be decompressed, perhaps by decompression software executed by the remote computer. Ideally, the decompressed data stream will be the same as the captured data stream. If it is the same, then the compression routine is termed xe2x80x9clossless compression;xe2x80x9d that is, the compression involved no loss of information. However, if the decompressed data stream is different, even slightly different, than the captured data stream, the compression routine is termed xe2x80x9clossy compression.xe2x80x9d Some information was xe2x80x9clostxe2x80x9d during compression and so the captured data stream could not be recovered exactly.
Some applications require that the compression be performed losslessly. For example, a pen-based computer used in commercial transactions may require that signatures transmitted to facilitate credit card payments be transmitted losslessly. Understandably, a merchant and customer may demand that signature verification be performed with the highest respect for integrity of the data stream and that no information be lost during compression. In contrast, the transmission of animated cartoons may be performed in a lossy manner. Even though the original data stream is not faithfully recovered or extracted, the user of the pen-based computer may not care and may tolerate the loss of information.
U.S. Pat. No. 6,011,873 to Desai, et al. (Penware, Inc.) describes a compression algorithm for lossless compression of signature data. The Desai algorithm computes the differential between consecutive points in a data stream to achieve compression. This algorithm discards duplicate data points and achieves some compression of the captured data stream for certain types of digital ink. Only discarding duplicate data points and only taking the differential between consecutive points limits the amount of compression that is achieved. If the consecutive points in the data stream are not highly correlated (e.g., such as with jittery handwritten lines, computer images or graphic animations), then using the Desai algorithm to perform compression produces a compressed data stream which is not optimally compressed, and may even be larger than the captured data stream.
Improved compression systems and methods would be desirable, particularly for very small portable devices that carry out compression of digital ink. Accordingly, particularly for very small portable devices such as pen-based computer systems, and other hand held appliances that utilize compression, there is a need for efficient new systems for compression of digital ink.
Various aspects of the invention are described in more detail in the following Drawings and Detailed Description of the Invention.